package code201_300.code10_20;

import java.util.HashSet;

/**
 * 给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的 绝对值 至多为 k。
 *
 * 输入: nums = [1,2,3,1], k = 3
 * 输出: true
 *
 * 输入: nums = [1,0,1,1], k = 1
 * 输出: true
 *
 * 输入: nums = [1,2,3,1,2,3], k = 2
 * 输出: false
 *
 */
public class _219containsNearbyDuplicate {

    /**
     * 思考：只能用普通方法来做，再优一点的方法是每次滑动窗口，滑动特定步长
     *
     * 执行用时：     * 2090 ms     * , 在所有 Java 提交中击败了     * 5.02%     * 的用户
     * 内存消耗：     * 50.3 MB     * , 在所有 Java 提交中击败了     * 43.84%     * 的用户
     *
     * @param nums
     * @param k
     * @return
     */
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        if(nums.length<2)return false;
        if(nums.length<=k)k = nums.length-1;
        for (int i = 0; i <= nums.length-1; i++) {
            for (int j = i+1; j <= i+k; j++) {
                if(j>nums.length-1)continue;
                if(nums[i] == nums[j]){
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 固定滑动窗口:空间换时间，时间复杂度位O(n)
     * 和上题一样，用set来完成判断，单词循环即可
     *
     * 执行用时：     * 18 ms     * , 在所有 Java 提交中击败了     * 90.59%     * 的用户
     * 内存消耗：     * 53.1 MB     * , 在所有 Java 提交中击败     * 19.40%     * 的用户
     *
     * @param nums
     * @param k
     * @return
     */
    public boolean containsNearbyDuplicate1(int[] nums, int k) {
        //特殊情况
        if (nums.length == 0) {
            return false;
        }
        // set
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; ++i) {
            //含有该元素，返回true
            if (set.contains(nums[i])) {
                return true;
            }
            // 添加新元素
            set.add(nums[i]);
            //维护窗口长度
            if (set.size() > k) {
                set.remove(nums[i-k]);
            }
        }
        return false;
    }

}
